package com.example.demo.Calss18_dongtaiguihua;

/**
 * @program: java_base
 * @description: 动态规划
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/03 10:03
 */
public class Code01_RobotWalkDemo {


    /**
     * 非动态递归
     *
     * @param cur  当前节点
     * @param rest 还有rest步去走
     * @param aim  目标位置，最终要走到的点
     * @param N    区间范围 1~N
     * @return 返回从cur出发，走过rest步后，最终停留在aim位置，有多少种走法？
     */
    public static int process1(int cur, int rest, int aim, int N) {
        if (rest == 0) {
            return cur == aim ? 1 : 0;
        }
        if (cur == 1) {
            // 站在 1点上，只能向2方向走，就等于 在2位置剩余步骤-1种可能
            return process1(2, rest - 1, aim, N);
        }
        if (cur == N) {
            // 站在 1点上，只能向2方向走，就等于 在2位置剩余步骤-1种可能
            return process1(N - 1, rest - 1, aim, N);
        }
        // 除去 最左边 和 最右边 之间的节点 返回可能性
        return process1(cur - 1, rest - 1, aim, N)
                + process1(cur + 1, rest - 1, aim, N);
    }

    // 动态规划，傻缓存法！

    /**
     * 从顶向下的动态规划
     * 或者叫记忆化搜索
     *
     * @param cur
     * @param rest
     * @param aim
     * @param N
     * @param dp   因为 路径相同的点，结果一样，顾可以使用缓存，dp需要初始化-1的值。
     * @return dp 缓存为 cur 和 rest 组成
     */
    public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = process2(2, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = process2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = process2(cur - 1, rest - 1, aim, N, dp) +
                    process2(cur + 1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

    /**
     * [解释](https://www.mashibing.com/study?courseNo=339&sectionNo=744)
     * 此矩阵 有 行：cur（所有cur枚举）  列：k（总步数） 组成，分析推算目标 aim k 坐标对应的值
     *
     * @return
     */
    /** 根据递归序列 逆推回
     *
     * @param N 1~N 个数
     * @param start 开始点
     * @param aim   目标点
     * @param k     走的步数
     * @return
     */
    public static int process3(int N, int start, int aim, int k) {
        int[][] dp = new int[N + 1][k + 1];
        dp[aim][0] = 1;

        // 外 --列
        for (int col = 1; col <= k; col++) {
            // 内 行
            // row 从2开始： dp[1][col] = dp[2][col-1]
            dp[1][col] = dp[2][col - 1];
            for (int row = 2; row < N; row++) {
                dp[row][col] = dp[row - 1][col - 1]
                        + dp[row + 1][col - 1];
            }
            dp[N][col] = dp[N - 1][col-1];
        }
        return dp[start][k];
    }

}
